import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/1 11:40
 * @description 思路：跟886题类似，对于i节点，假设他在A子集中，那么所有与他相连的点都需要防止在B子集中，dfs如果发生冲突那么就无法二分
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] graph = {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
        solution.isBipartite(graph);
    }

    Map<Integer, Integer> color;

    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        color = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (!color.containsKey(i) && !dfs(graph, i, 0)) {
                return false;
            }
        }
        return true;
    }

    public boolean dfs(int[][] graph, int i, int c) {
        if (color.containsKey(i)) {
            // 已经染色过，那么判断将要的染色是否和旧的一致，即是否分配到一个集合中
            return color.get(i) == c;
        }
        // 没有，那么染色
        color.put(i, c);
        // 所有和i节点相连的y节点，都要分配到另一个集合中
        for (int y : graph[i]) {
            if (!dfs(graph, y, c ^ 1)) {
                return false;
            }
        }
        return true;
    }
}
